﻿/* 15. Write a program that finds all prime numbers in the range [1...10 000 000]. 
 * Hint: Use the sieve of Eratosthenes algorithm. */

using System;

public class PrimeNumbers
{
    public static void Main()
    {
        int upperNumber = 10000000;
        int upperBound = (int)Math.Sqrt(upperNumber);
        int[] allNumbers = new int[upperNumber + 1];

        Console.Write("\nIn range [1, {0}] ", upperNumber);

        if (upperNumber < 2)
            Console.WriteLine("there is no prime number!\n");
        else if (upperNumber == 2)
            Console.WriteLine("the unique prime number is 2.");
        else if (upperNumber == 3)
            Console.WriteLine("all prime numbers are {0} 2, 3 {1}\n", "{", "}");
        else
        {
            for (int i = 0; i <= upperNumber; i++)
                allNumbers[i] = i;

            Console.Write("all prime numbers are\n{0} 2", "{");

            int prime = 2;

            for (int eraser = prime * prime; eraser <= upperNumber; eraser += prime)
                allNumbers[eraser] = 0;

            prime = 3;
            for (; prime <= upperBound; prime++)
            {
                if (allNumbers[prime] == 0)
                    continue;

                Console.Write(", {0}", prime);
                for (int eraser = prime * prime; eraser <= upperNumber; eraser += prime)
                    allNumbers[eraser] = 0;
            }

            for (int rests = upperBound + 1; rests <= upperNumber; rests++)
                if (allNumbers[rests] > 0)
                    Console.Write(", {0}", rests);

            Console.WriteLine(" {0}\n", "}");
        }
    }
}